P4400 [JSOI2008]Blue Mary的旅行

这道题貌似很多人用的是网络流+分层图。这里介绍一种费用流解法。

可以证明，最后一个人到达的时间是小于第100天的。

那么对于每一趟航班，如果他的起点是$u$，终点为$v$，可搭乘的人的数量为$w$。那我们就对$(u,v)$连100条流量为$w$,费用为$i$的边（$i$表示第几天），分别表示第$i$天的航班。

我们跑费用流时，也不是计算最短距离，而是找到起点到终点的一条路径上的一条费用最大的边的最小值。

比如

我们要的路径是$A \to C \to D$,因为$max(AC,CD)<max(AB,BD)$

跑一个流量为$t$的费用流即可。

最后，关于$spfa$，它活了。（貌似只有几十毫秒）。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f

const int MAXN = 5005;
int flow , cost;
int n , m , u , v , w , f;
struct node{
	int v , w , f , rev;
};
vector< node > Graph[ MAXN + 5 ];

int dis[ MAXN + 5 ] , vis[ MAXN + 5 ];
int prevv[ MAXN + 5 ] , preve[ MAXN + 5 ];
void spfa( int s , int t ) {
	queue< int > Que;
	memset( dis , 0x3f , sizeof( dis ) );
	memset( vis , 0 , sizeof( vis ) );

	dis[ s ] = 0 , vis[ s ] = 1 , Que.push( s );
	while( !Que.empty( ) ) {
		int u = Que.front( );
		Que.pop( ) , vis[ u ] = 0;

		for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
			int v = Graph[ u ][ i ].v , w = Graph[ u ][ i ].w;
			if( w <= dis[ u ] ) continue;	//保证一天只坐一班飞机
			if( Graph[ u ][ i ].f && dis[ v ] > max( dis[ u ] , w ) ) {
				dis[ v ] = max( dis[ u ] , w );
				prevv[ v ] = u , preve[ v ] = i;
				if( !vis[ v ] )
					Que.push( v ) , vis[ v ] = 1;
			}
		}
	}
}
void Costflow( int S , int T ) {
	while( 1 ) {
		spfa( S , T );
		if( !flow || dis[ T ] == INF ) return;
		
		int d = INF;
		for( int v = T ; v != S ; v = prevv[ v ] )
			d = min( d , Graph[ prevv[ v ] ][ preve[ v ] ].f );
		flow -= d , cost = max( cost , dis[ T ] );
		for( int v = T ; v != S ; v = prevv[ v ] ) {
			Graph[ prevv[ v ] ][ preve[ v ] ].f -=d;
			Graph[ v ][ Graph[ prevv[ v ] ][ preve[ v ] ].rev ].f += d;
		}
	}
}

int main( ) {
	scanf("%d %d %d",&n,&m,&flow);
	for( int i = 1 ; i <= m ; i ++ ) {
		scanf("%d %d %d",&u,&v,&f);
		for( int j = 1 ; j <= 105 ; j ++ ) {
			w = j;
			Graph[ u ].push_back( { v , w , f , Graph[ v ].size( ) } );
			Graph[ v ].push_back( { u , -w , 0 , Graph[ u ].size( ) - 1 } );
		}
	}
	Costflow( 1 , n );
	printf("%d\n",cost);
	return 0;
}